W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Sieć kolejowa Bajtockich Kolei Bitowych (BKB) składa się z dwukierunkowych odcinków torów łączących pewne pary stacji. Każda para stacji jest połączona co najwyżej jednym odcinkiem torów. Ponadto wiadomo, że z każdej stacji kolejowej można dojechać do każdej innej dokładnie jedną trasą. (Trasa może być złożona z kilku odcinków torów, ale nigdy nie przechodzi przez żadną stację więcej niż raz).
Bajtazar jest tajnym inspektorem BKB. W celu przeprowadzenia inspekcji wybiera jedną ze stacji (oznaczmy ją ), w której organizuje sobie centralę, i rozpoczyna podróż po wszystkich innych stacjach. Podróż ma następujący przebieg:
Bajtazar pragnie rozważyć wszystkie możliwe stacje jako stacje początkowe . Dla każdej z nich chcemy wyznaczyć kolejność, w jakiej Bajtazar powinien kontrolować pozostałe stacje, tak aby łącznie jak najmniej czasu spędził na przejazdach, o ile dla danej stacji w ogóle taka kolejność istnieje.
Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą (), oznaczającą liczbę stacji. Stacje są ponumerowane od 1 do . Kolejne wierszy opisuje odcinki torów, po jednym w wierszu. W każdym z nich znajdują się dwie liczby całkowite (, ), oddzielone pojedynczym odstępem, oznaczające, że istnieje odcinek torów łączący stacje i . Każdy odcinek torów pojawia się w opisie dokładnie raz.
W testach wartych przynajmniej 30% punktów zachodzi dodatkowy warunek .
Twój program powinien wypisać na standardowe wyjście wierszy, a w każdym z nich po jednej liczbie całkowitej. Liczba w -tym wierszu powinna być równa minimalnej liczbie godzin, jakie Bajtazar musi spędzić na przejazdach, aby skontrolować stacje, dla - o ile dla szukana kolejność stacji istnieje. W przeciwnym przypadku, w -tym wierszu powinna znaleźć się liczba .
Dla danych wejściowych:
9 3 6 2 4 2 6 2 5 1 7 2 7 8 9 7 8
poprawną odpowiedzią jest:
-1 23 -1 -1 -1 -1 -1 -1 -1
Rysunek pokazuje przykładową sieć połączeń.
Szukana kolejność, w jakiej Bajtazar powinien kontrolować stacje, istnieje tylko dla .
Może to być na przykład: , , , , , , , .
Przy takiej kolejności kontrolowanych stacji Bajtazar spędzi na przejazdach łącznie godziny.
Autorzy zadania: Wojciech Rytter i Bartosz Szreder.